package uestc.lj.basic.sort;

import java.util.Arrays;

/**
 * 归并排序
 *
 * @Author:Crazlee
 * @Date:2021/11/20
 */
public class Code06_MergeSort {

    public static void mergeSort(int[] array) {
        if (array == null || array.length < 2) {
            return;
        }
        process(array, 0, array.length - 1);
    }

    public static void process(int[] array, int left, int right) {
        if (left == right) {
            return;
        }
        int mid = left + ((right - left) >> 1);
        process(array, left, mid);
        process(array, mid + 1, right);
        merge(array, left, mid, right);
    }

    public static void merge(int[] array, int left, int mid, int right) {
        //辅助数组用来merge
        int[] help = new int[right - left + 1];
        int i = 0;
        //分别遍历 left——mid 和 mid+1——right
        int p1 = left;
        int p2 = mid + 1;
        while (p1 <= mid && p2 <= right) {
            help[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++];
        }
        while (p1 <= mid) {
            help[i++] = array[p1++];
        }
        while (p2 <= right) {
            help[i++] = array[p2++];
        }
        if (help.length >= 0) {
            System.arraycopy(help, 0, array, left, help.length);
        }
    }

    public static void main(String[] args) {
        int[] array = {5, 7, 8, 2, 6, 1, 9, 3, 4};
        System.out.println("归并排序之前数组元素为：");
        Arrays.stream(array).forEach(value -> System.out.print(value + " "));
        mergeSort(array);
        System.out.println();
        System.out.println("归并排序之后数组元素为：");
        Arrays.stream(array).forEach(value -> System.out.print(value + " "));
    }
}
